/*-------------------------------------------------------------------------*/
/**
  @file		mlp.c
  @author	Renaud Wanchoor
  @date	July 2004
  @version	$Revision: 2.16 $
  @brief	multilevel graph partitioning
  @update date	March 2007 by Xiaochen Wu
  
*/
/*--------------------------------------------------------------------------*/
#include "pagrid.h"
#include <sys/time.h>
/**
 * \brief multilevel graph partitioning
 *
 * Partition the graph file onto the grid using info params
 * \param graph application graph
 * \param grid computational grid
 * \param info parameters for partitioning
 */

void MultiLevelPartition(GraphType *graph, GridType *grid, PartInfoType *info){ 
        /*Statistic INfo*/
	int i;			
	int *guide = NULL;
	int dummy;
	char *nullchar = NULL;

	info->rtimer[1] = gettimes();	
	info->level = -1;
	info->currLevel = -1;

	/**************************************/
	/*                                    */
	/*        Coarsening Stage            */
	/*                                    */
	/**************************************/
	/* unserialize matching */
	if(info->out[IO_SER] == IO_SER_USE){
	  graph = Pagrid_Unserialize(info->F_serialize,graph,
				     &(nullchar),&(nullchar),
				     &(info->level), 
				     &(info->CType), &(info->WType), &dummy,
				     &info->CSeed, &dummy, &dummy);
	/* compute matchings */
	}else{
	  ran_start(info->CSeed);
	  graph = Coarsen(graph, grid, info);
	}
	
	/**************************************/
	/*                                    */
	/*       Initial Partitionning        */
	/*                                    */
	/**************************************/
	info->rtimer[2] = gettimes();	
	ran_start(info->ISeed);
	switch(info->RType){
	case IO_UNCO_KLEXEC:
	  InitialPartExec(graph, grid);
	  break;
	}

	/* serialize matching */
	if(info->out[IO_SER] == IO_SER_DO){
	  Pagrid_Serialize(graph,info->F_serialize,info->out[IO_RESULT],
			   info->out[IO_ID],
			   info->F_graph,info->F_grid,
			   info->CType,info->WType,info->RType,
			   info->CSeed,info->ISeed,info->RSeed);
	}

	
	/* serialize refinement*/
	if(info->out[IO_SER] != IO_SER_NONE)
	  Pagrid_SerializeWhere(graph,info->F_output,info->out[IO_ID],
				info->out[IO_RESULT],info->out[IO_SER]);

	/**************************************/
	/*                                    */
	/*       Refinement stage             */
	/*                                    */
	/**************************************/
        /*                                    */
	/*       Init                         */
	/*                                    */
	/**************************************/

	ran_start(info->RSeed);
	switch(info->RType){	
	case IO_UNCO_KLEXEC:
	  /** -- REMOVE -- **/
	  for (i=0; i<grid->npro; i++){
	    printf("processor %2d : %5d vertices %10.2f execution time\n", graph->pro[i], graph->vwgt[i], grid->exec[graph->pro[i]]);
	  }
	  printf("\n");
	  /** -- END REMOVE -- **/
	  printf("---------------------------------------------------------------------------------------------------------------------------\n");
	  break;
	}

	/**************************************/
        /*                                    */
	/*       Uncoarsening phase           */
	/*                                    */
	/**************************************/
	info->rtimer[3] = gettimes();	
        int moves = 0;
	for (i=info->level; i>0; i--){
	  /***********************/
	  /* serialize refinement*/
	  if(info->out[IO_SER] != IO_SER_NONE)
	    Pagrid_SerializeWhere(graph,info->F_output,info->out[IO_ID],
				  info->out[IO_RESULT],info->out[IO_SER]);
	  /***********************/

	  info->currLevel = i;

	  /*Project Back the coarer graph*/
	  ProjBack(graph, grid, info);	
	  
	  graph = graph->father;
	  LIBG_Free(graph->child);	  
	  
	  guide = U_malloc(graph->nvtxs,int,"MultiLevelPartition error code 5\n");
	  randnum(graph->nvtxs, guide);

	  /*Refinement*/
	  switch(info->RType){
	  case IO_UNCO_KLEXEC:
            Init_Connect(graph, grid);
	    SwapProcessors(grid,graph);
	    moves += execRefine(graph,grid,i-1,guide,info);	
	    break;
	  }
	  U_free("MultiLevelPartition error code 6\n",&guide,LEND);
	}
	printf("---------------------------------------------------------------------------------------------------------------------------\n");
	/***********************/
	/* serialize refinement*/
	if(info->out[IO_SER] != IO_SER_NONE)
	  Pagrid_SerializeWhere(graph,info->F_output,info->out[IO_ID],
				info->out[IO_RESULT],info->out[IO_SER]);
	/***********************/
	/** -- REMOVE -- **/
	{
	  
	  double* volet;
	  double volmet;
	  int* npro      = grid->app->pro;
	  int* nadjidx   = grid->app->adjidx;
	  int* nadjncy   = grid->app->adjncy;
	  int** connect  = grid->connect;
	  int** latency1 = grid->latency1;
	  int j,jstart,jend;

	  switch(info->RType){
	  case IO_UNCO_KLEXEC:
	    /* Compute Estimated execution time with full latency weight */
	    ExecTime_FullWeight(graph, grid);
	    IO_statVol(TOOL_PAGRID,graph,grid,&volmet,&volet);
	    for(i = 0; i < grid->npro; i++){
	      for(j = 0; j < grid->npro; j++){
	        if(connect[i][j] > 0){
	          volet[i] += latency1[i][j];
	        }
	      }
	    }

	    printf("\n");
	    for (i=0; i<grid->npro; i++){
	      printf("processor %2d : %5d vertices %10.2f (%10.2f) execution time adj : ", 
		     npro[i], grid->app->vwgt[i], grid->exec[npro[i]], volet[npro[i]]);
	      
	      jstart = nadjidx[i];
	      jend   = nadjidx[i+1];
	      
	      for(j=jstart;j<jend;j++){
		printf("%2d ",npro[nadjncy[j]]);
	      }
	      printf("\n");
	    }
	    printf("\n");
	    U_free("mlp.c volmet debug free error\n",&volet,LEND);
	    break;
	  }
	}
	/** -- END REMOVE -- **/

	/**************************************/
	/*                                    */
	/*              Finalize              */
	/*                                    */
	/**************************************/	
	info->rtimer[4] = gettimes();
	
	/**************************************/
        /*                                    */
	/*       output                       */
	/*                                    */
	/**************************************/	

	info->cputime[0] = info->rtimer[4] - info->rtimer[0]; /* total */
	info->cputime[1] = info->rtimer[2] - info->rtimer[1]; /* coarsening */
	info->cputime[2] = info->rtimer[3] - info->rtimer[2]; /* initial partitioning */
	info->cputime[3] = info->rtimer[4] - info->rtimer[3]; /* refinement */
}

/**
 * \Compute estimated execution time with full latency weight
 *
 * \param graph application graph
 * \param grid computational grid
 */
void ExecTime_FullWeight(GraphType* graph, GridType* grid){
  int i,j;
  double *exec = grid->exec;
  int nnpro = grid->npro;
  int istart,iend;
  int v,prov,w, prow;
  double *prospeed = grid->prospeed;
  int *adjidx = graph->adjidx;
  int *adjncy = graph->adjncy;
  int *adjwgt = graph->adjwgt;
  int *pro = graph->pro;
  int *vwgt = graph->vwgt;
  int nvtxs = graph->nvtxs;
  double **ratio = grid->ratio;
  int **connect = grid->connect;
  int **latency1 = grid->latency1;

  for(i = 0; i < nnpro; i++)
    exec[i] = 0;
  for(v = 0; v < nvtxs; v++){
    prov = pro[v];
    exec[prov] += vwgt[v]*prospeed[prov];
    istart = adjidx[v];
    iend = adjidx[v+1];
    for(i = istart; i < iend; i++){
      w = adjncy[i];
      prow = pro[w];
      if(prov != prow){
        exec[prov] += adjwgt[i] * ratio[prov][prow];
      }
    }
  }
  for(i = 0; i < nnpro; i++){
    for(j = 0; j < nnpro; j++){
      if(connect[i][j] > 0)
        exec[i] += latency1[i][j];
    }
  }
}

